from typing import List, Any, Iterator, Tuple, Dict
from collections import Iterable

class TreeNode(object):
    def __init__(self, value : None) -> None:
        self.value = value
        self.left = None
        self.right = None
        self.visited_count = 0
        self.is_leaf = False
    
class BinaryTree(object):
    def __init__(self, *args) -> None:
        self.root : TreeNode = None
        if len(args)!=0 :
            self.create(args[0])
    
    
    def create(self, values : List[Any]) -> None:
        if isinstance(values, Iterable):
            for i, item in enumerate(values):
                self.add(item) #get the first params
        else:
            raise ValueError("invalid init values, as they are not iterable")
    
    def add(self, value : Any) -> TreeNode:
        if self.root is None :
           self.root = TreeNode(value) 
           return
       
        queque : List[TreeNode]= []
        queque.append(self.root) 
        node : TreeNode = TreeNode(value)
        while queque :
            front = queque.pop(0)
            if front is not None: 
                if front.left is None:
                    front.left = node
                    return 
                else:
                    queque.append(front.left)
                    
                if front.right is None:
                    front.right = node
                    return 
                else:
                    queque.append(front.right)

    def BFS(self) -> List[Any]:
        ''''
        @level visiting, visit left node before right node
        '''
        if self.root is None:
            return
        
        res : List[Any]= []
        
        queque : List[TreeNode] = list()
        queque.append(self.root)
        
        right_node = self.root
        while len(queque) > 0 :
            front = queque.pop(0)
            res.append(front.value)
            
   
                
            if front.left is not None:
                queque.append(front.left)
            if front.right is not None:
                queque.append(front.right)
            
            if(right_node == front):
                right_node =right_node.right    
        return res
    
    def DFS(self) -> List[Any]:
        '''
        algorithm idea:
        首先判断根是否为空，将根节点入栈
        1.若栈为空，则退出循环 
        2.将栈顶元素弹出，访问弹出的节点 
        3.若弹出的节点的右孩子不为空则将右孩子入栈 
        4.若弹出的节点的左孩子不为空则将左孩子入栈 
        '''
        if self.root is None:
            return
        
        res : List[Any]= []
        
        stack : List[Any]= list()
        stack.append(self.root)
           
        while len(stack) > 0 :
            top_node = stack.pop()
            res.append(top_node.value)

            if top_node.right is not None:
                stack.append(top_node.right)
            if top_node.left is not None:
                stack.append(top_node.left)
            
        return res
    
    def pre_order_travelsal_1(self) -> List[Any]:
        if self.root is None:
            return
        
        res : List[Any]= []
        
        stack : List[Any]= list()

        pNode : TreeNode[Any] = self.root
        while pNode is not None or len(stack) > 0: 
            if (pNode is not None) :
                res.append(pNode.value)
                stack.append(pNode)
                pNode = pNode.left
            else:  #pNode == null && !stack.isEmpty() 
                '''
                当pNode为空时,说明已经到达左子树最下边, 而此时的栈顶元素则是最左侧的叶子节点，接下来要访问其右子树
                '''
                node : TreeNode[Any] = stack.pop()
                pNode = node.right
        return res
    
    def pre_order_travelsal_2(self) -> List[Any]:
        if self.root is None:
            return
        
        res : List[Any]= []
        
        stack : List[Any]= list()

        pNode : TreeNode[Any] = self.root
        while pNode is not None or len(stack) > 0: 
            while (pNode is not None) :
                '''
                一路移动指针，一路保存节点，直至遇到叶子结点后面的空节点
                '''
                res.append(pNode.value)
                stack.append(pNode)
                pNode = pNode.left
            if len(stack) > 0 : 
                '''
                当pNode为空时,说明已经到达左子树最下边, 而此时的栈顶元素则是最左侧的叶子节点，接下来要访问其右子树
                '''
                node : TreeNode[Any] = stack.pop()
                pNode = node.right
        return res
    def pre_order_travelsal_3(self) -> List[Any]:
        if self.root is None:
            return
        
        res : List[Any]= []
        
        stack : List[Any]= list()

        stack.append(self.root)
        
        while len(stack) > 0:
            node =  stack.pop()
            
            if (node.is_leaf == True) or node.visited_count ==1:
               res.append(node.value)
               node.visited_count = 0  
            else:
                if node.right is not None:
                    stack.append(node.right)
   
                if node.left is not None:
                    stack.append(node.left)
                    
                if node.right is None and node.left is None:
                    node.is_leaf = True
                    
                stack.append(node)    
                node.visited_count +=1
                
        return res
    
    def middle_order_travelsal_1(self) -> List[Any]:
        if self.root is None:
            return
        
        res : List[Any]= []
        
        stack : List[Any]= list()

        pNode : TreeNode[Any] = self.root
        while pNode is not None or len(stack) > 0: 
            if (pNode is not None) :
                stack.append(pNode)
                pNode = pNode.left
            else:  #pNode == null && !stack.isEmpty()
                node : TreeNode[Any] = stack.pop()
                res.append(node.value)
                pNode = node.right
        return res
    
    def middle_order_travelsal_2(self) -> List[Any]:
        if self.root is None:
            return
        
        res : List[Any]= []
        
        stack : List[Any]= list()

        stack.append(self.root)
        
        while len(stack) > 0:
            node =  stack[-1]
            if (node.is_leaf == True) or node.visited_count ==1:
               res.append(node.value)
               node.visited_count = 0  
               stack.pop()
            else:
                if node.right is not None:
                    root_node = stack.pop()
                    stack.append(node.right)
                    stack.append(root_node)
   
                if node.left is not None:
                    stack.append(node.left)
                    
                if node.right is None and node.left is None:
                    node.is_leaf = True
                    
                node.visited_count +=1
                
        return res
    
    def post_order_travelsal_1(self) -> List[Any]:
        '''
        @post visit oder: left node, right node, root node
        '''
        if self.root is None:
            return
        
        res : List[Any]= []
        
        stack : List[Any]= list()
        stack.append(self.root)
        
        while len(stack) > 0:
            top_node = stack[-1]            
            
            # two cases should be visited and pop() the node
            if (top_node.left is None and top_node.right is None) or (top_node.visited_count ==2): 
                res.append(top_node.value)
                top_node.visited_count = 0 
                stack.pop()
                
            else:
                if top_node.visited_count == 0: # visit left firstly
                    if top_node.left is not None:
                        stack.append(top_node.left)
                        
                if top_node.visited_count == 1:
                    if top_node.right is not None:
                        stack.append(top_node.right)
                
                top_node.visited_count +=1
                
        return res
    def post_order_travelsal_3(self) -> List[Any]:
        '''
        @post visit oder: left node, right node, root node
        '''
        if self.root is None:
            return
        
        res : List[Any]= []
        
        stack : List[Any] = list()
   
        stack.append(self.root)
        
        while len(stack) > 0:
            node =  stack[-1]
            if (node.is_leaf == True) or node.visited_count == 1:
               #print([item.value for i, item in enumerate(stack)],node.value, node.visited_count, node.leaf)
               res.append(node.value)
               node.visited_count = 0 
               stack.pop()
               
            else:   
                if node.right is not None:
                    stack.append(node.right)

                if node.left is not None:
                    stack.append(node.left)

                if node.right is None and node.left is None:
                    node.is_leaf = True
                    
                node.visited_count += 1        
                
        return res
        
    def post_order_travelsal_2(self) -> List[Any]:
        '''
        algorithm idea:
        由于：
            前序：根->左->右 
            后序：左->右->根
        那么，
        可以把后序遍历结果：根->右->左，看做是前序遍历的逆序
        action:可利用双栈策略，用一个栈保存前序遍历结果，最后顺序出栈即可
        But!!!!!!!! 复杂度稍高一些,不建议！！！
        '''
        if self.root is None:
            return
        
        res : List[Any]= []
        stack1 : List[Any]= list()
        stack2 : List[Any]= list()
        stack1.append(self.root)
        while len(stack1) > 0 :
            node = stack1.pop()
            stack2.append(node) #stack1 前序遍历的结果
            if node.left:
                stack1.append(node.left)
            if node.right:
                stack1.append(node.right)

        while len(stack2) > 0 :  # 将 stack2中的元素出栈，即是后序遍历序列
            res.append(stack2.pop().value)
            
        return res       
    
    def level_from_top_r2l(self) -> List[Any]:
        '''
        @level visiting, visit right node before left node
        '''
        if self.root is None:
            return
        
        res : List[Any]= []
        
        stack : List[Any]= list()
        stack.append(self.root)
        res.append(self.root.value)
        
        while len(stack) > 0 :
            top_node = stack.pop()
            if top_node.right is not None:
                res.append(top_node.right.value)
                stack.append(top_node.right)
            if top_node.left is not None:
                res.append(top_node.left.value)
                stack.append(top_node.left)
    
        return res 
    
    def pre_oder_travelsal(self) -> List[Any]:     
        if self.root is None:
            return None
        
        stack : List[Any]= list()
        res : List[Any]= list()
        
        stack.append(self.root)

        while(len(stack) > 0):
            top_node = stack.pop()
            
            if ( top_node.visited_count == 1) or (top_node.right is None and top_node.left is None):
                res.append(top_node.value)
                top_node.visited_count = 0
   
                continue

            if top_node.right is not None:
                stack.append(top_node.right)
            if top_node.left is not None:
                stack.append(top_node.left)
                
            top_node.visited_count = 1
            stack.append(top_node)
                    
        return res    
    
    def middle_oder_travelsal(self) -> List[Any]:     
        if self.root is None:
            return None
        
        stack : List[Any]= list()
        res : List[Any]= list()
        
        stack.append(self.root)

        while(len(stack) > 0):
            top_node = stack.pop()
   
            if ( top_node.visited_count == 1) or (top_node.right is None and top_node.left is None):
                res.append(top_node.value)
                top_node.visited_count = 0
                continue
                 
            if top_node.right is not None:
                stack.append(top_node.right)
                
            stack.append(top_node)
            top_node.visited_count = 1
                
            if top_node.left is not None:
                stack.append(top_node.left)    
               
        return res    
    
    def post_oder_travelsal(self) -> List[Any]:     
        if self.root is None:
            return None
        
        stack : List[Any]= list()
        res : List[Any]= list()
        
        stack.append(self.root)

        while(len(stack) > 0):
            top_node = stack.pop()
            
            if ( top_node.visited_count == 1) or (top_node.right is None and top_node.left is None):
                res.append(top_node.value)
                top_node.visited_count = 0
                continue
            
            stack.append(top_node)
            top_node.visited_count = 1
                 
            if top_node.right is not None:
                stack.append(top_node.right)
                
            if top_node.left is not None:
                stack.append(top_node.left)    
                
        return res
    
    def allpath(self) -> List[Any]:     
        if self.root is None:
            return None
        
        stack : List[Any]= list()
        res : List[Any]= list()
        
        stack.append(self.root)

        while(len(stack) > 0):
            top_node = stack.pop()
            
            if ( top_node.visited_count == 1) or (top_node.right is None and top_node.left is None):
                res.append(top_node.value)
                top_node.visited_count = 0

                if (top_node.right is None and top_node.left is None):  
                    all_path_node = []
                    for item in stack:
                        if item.visited_count == 1:
                            all_path_node.append(item.value)
                    all_path_node.append(top_node.value)
                    res.append(all_path_node)  
                    
                continue
            
            stack.append(top_node)
            top_node.visited_count = 1
                 
            if top_node.right is not None:
                stack.append(top_node.right)
                
            if top_node.left is not None:
                stack.append(top_node.left)    
                
        return res
       
    def every_level_node(self) -> List[Any]:
        ''''
        @level visiting, visit left node before right node
        '''
        if self.root is None:
            return

        queque : List[TreeNode] = list()
        queque.append(self.root)
        
        all_level_node = []
        import copy
        level_queque = copy.deepcopy(queque)
        all_level_node.append([item.value for item in level_queque])
        
        while len(queque) > 0 :
            front = queque.pop(0)

            if front.left is not None:
                queque.append(front.left)
            if front.right is not None:
                queque.append(front.right)
                
            
            level_queque.pop(0)
            if (len(level_queque)==0) and (len(queque) >0):
                level_queque = copy.deepcopy(queque)
                all_level_node.append([item.value for item in level_queque])
                
   
        return all_level_node
         
    def get_right_nodes(self) -> List[Any]:
        ''''
        @level visiting, visit left node before right node
        '''
        if self.root is None:
            return
        
        queque : List[TreeNode] = list()
        queque.append(self.root)
        
        all_right_node = []
        import copy
        level_queque = copy.deepcopy(queque)
        all_right_node.append(level_queque[-1].value)
        
        while len(queque) > 0 :
            front = queque.pop(0)

            if front.left is not None:
                queque.append(front.left)
            if front.right is not None:
                queque.append(front.right)
                
            level_queque.pop(0)
            if (len(level_queque)==0) and (len(queque) >0):
                level_queque = copy.deepcopy(queque)
                all_right_node.append(level_queque[-1].value)
                
        return all_right_node
                
    def mirror_tree(self) -> TreeNode:
        if self.root is None:
            return None
        
        queque : List[TreeNode] = list()
        queque.append(self.root)
        
        while len(queque) > 0 :
            front = queque.pop(0)
            if front is not None:
                queque.append(front.left)
                queque.append(front.right)
                front.right, front.left = front.left, front.right
        
        return self.root
    
                   
if __name__ == '__main__':
    binaray_tree = BinaryTree([1,2,3,4,"A","B","C","D","E","F","G","H"])
    '''
    res = binaray_tree.BFS()
    print("BFS",res)
    res = binaray_tree.DFS()
    print("DFS",res)
    res = binaray_tree.pre_order_travelsal_1()
    print("pre_order_travelsal_1",res)
    res = binaray_tree.pre_order_travelsal_2()
    print("pre_order_travelsal_2",res)
    res = binaray_tree.pre_order_travelsal_3()
    print("pre_order_travelsal_3",res)
    res = binaray_tree.middle_order_travelsal_1()
    print("middle_order_travelsal_1",res)
    res = binaray_tree.middle_order_travelsal_2()
    print("middle_order_travelsal_1",res)
    res = binaray_tree.post_order_travelsal_1()
    print("post_order_travelsal_1",res)
    res = binaray_tree.post_order_travelsal_2()
    print("post_order_travelsal_2",res)
    res = binaray_tree.post_order_travelsal_3()
    print("post_order_travelsal_3",res)
    res = binaray_tree.level_from_top_r2l()
    print("BFD",res)
    '''
    
    res = binaray_tree.BFS()
    print("BFS",res)
    
    res = binaray_tree.pre_oder_travelsal()
    print("pre_oder_travelsal",res)
    
    res = binaray_tree.middle_oder_travelsal()
    print("middle_oder_travelsal",res)

    res = binaray_tree.post_oder_travelsal()
    print("post_oder_travelsal",res)
    
    res = binaray_tree.allpath()
    print("allpath",res)
    
    res = binaray_tree.every_level_node()
    print("every_level_node ",res)
    
    res = binaray_tree.get_right_nodes()
    print("get_right_nodes ",res)
    
    res = binaray_tree.mirror_tree()
    res = binaray_tree.middle_oder_travelsal()
    print("mirror_tree ",res)
    
    
    













